package 力扣.树.前序遍历;

import java.util.Stack;

public class 验证二叉搜索树98 {
    public boolean isValidBST(TreeNode root) {
        return isPre(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isPre(TreeNode node,Long l, Long r){
        if (node == null){
            return true;
        }
        if (!(Long.valueOf(node.val) > l && Long.valueOf(node.val) < r)){
            return false;
        }

        return  isPre(node.left, l, Long.valueOf(node.val))&&
                isPre(node.right, Long.valueOf(node.val), r);
    }


    // Node 记录了:
    // 1. 原树的结点t
    // 2. 影子二叉树的结点(l, r)
    class Node {
        TreeNode orig;
        Long l;
        Long r;

        public Node(TreeNode orig, Long l, Long r) {
            this.orig = orig;
            this.l = l;
            this.r = r;
        }
    }
    public boolean isValidBST2(TreeNode root) {
        Stack<Node> stack = new Stack<Node>();
        // 从根结点开始
        Node n = new Node(root, Long.MIN_VALUE, Long.MAX_VALUE);
        // 注意这里是利用n来完成两棵树的遍历，所以需要利用n.t结点来判断
        while (n.orig != null || !stack.empty()) {
            while (n.orig != null) {
                // 判断结点是不是在给定的范围里面
                if (!(n.l < n.orig.val && n.orig.val < n.r)) {
                    return false;
                }
                stack.push(new Node(n.orig, n.l, n.r));
                // 在使用栈的时候，这两个的顺序不要乱!
                // 遍历影子二叉树的左子树
                n.r = Long.valueOf(n.orig.val);
                // 遍历原二叉树的左子树
                n.orig = n.orig.left;
            }
            n = stack.peek();
            stack.pop();
            // 下面的两个顺序不要乱!
            // 因为要走向右子树，更新左边间
            n.l = Long.valueOf(n.orig.val);
            // 开始遍历原二叉树的右子树
            n.orig = n.orig.right;
        }
        return true;
    }
   public boolean isValidBST1(TreeNode root) {
        Stack<Node> stack = new Stack<>();
        Node node = new Node(root, Long.MIN_VALUE, Long.MAX_VALUE);
        while (node.orig != null || !stack.isEmpty()){
            while (node.orig != null){
                Long val= Long.valueOf(node.orig.val);
                if (!(val > node.l && val < node.r)){
                    return false;
                }
                stack.push(new Node(node.orig, node.l, node.r));
                node.r = val;
                node.orig = node.orig.left;
            }
            node = stack.pop();
            node.l = Long.valueOf(node.orig.val);
            node.orig = node.orig.right;
        }
        return true;
   }
//前序遍历
    public boolean isValidBST3(TreeNode root) {
        if (root == null){
            return false;
        }
        flag3 = true;
        preDfs(root,Long.MIN_VALUE,Long.MAX_VALUE);
        return flag3;
    }
    private boolean flag3;
    private void preDfs(TreeNode root, Long minValue, Long maxValue) {
        if (root != null){
           Long val = Long.valueOf(root.val);
           if (minValue < val && val < maxValue){
               preDfs(root.left, minValue, val);
               preDfs(root.right, val, maxValue);
           }else {
               flag3 = false;
           }
        }
    }


}
